package 系统复习.贪心算法;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 */
public class L53 {

    public int maxSubArray(int[] nums) {

        if (nums.length == 1) return nums[0];

        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            sum = Math.max(sum, count);
            if (count <= 0) {
                count = 0;
            }
        }
        return sum;

    }

    public static void main(String[] args) {
        L53 l53 = new L53();
        int i = l53.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        System.out.println(i);
    }

}
